package cz.cvut.fit.crhonjar.mi.paa.thames.solver;

import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;

import cz.cvut.fit.crhonjar.mi.paa.thames.Configuration;
import cz.cvut.fit.crhonjar.mi.paa.thames.Item;
import cz.cvut.fit.crhonjar.mi.paa.thames.exception.ThamesException;

/**
 * @author Jarec
 * 
 */
public class BranchAndBoundSolver extends Solver {

	@Override
	public Configuration solve() throws ThamesException {
		final Stack<Configuration> stack = new Stack<Configuration>();
		Collections.sort(this.items, new Comparator<Item>() {

			@Override
			public int compare(final Item o1, final Item o2) {
				return o2.getPrice() - o1.getPrice();
			}

		});
		Configuration conf = new Configuration(this.items);
		Configuration best = conf;
		stack.push(conf);

		// recursion converted to iteration
		while (!stack.isEmpty()) {
			conf = stack.pop();

			// do i have better solution
			if (conf.getPrice().intValue() > best.getPrice().intValue()) {
				best = conf;
			}

			// expand
			if (conf.getDepth().intValue() < this.items.size()) {
				conf.increaseDepth();

				stack.push(conf);

				// if bag wont be overloaded
				if ((conf.getWeight().intValue() + this.items
						.get(conf.getDepth() - 1).getWeight().intValue()) <= this.capacity
						.intValue()) {

					// branch and bound if
					if ((conf.getPrice() + conf.priceLeft()) > best.getPrice()) {
						final Configuration second = new Configuration(conf);
						second.addItem(conf.getDepth().intValue() - 1);

						stack.push(second);
					}

				}
			}
		}

		return best;
	}

}
